//
//  ArraySequence.m
//  iOS-Learning-Demo
//
//  Created by yuan xiaodong on 2022/3/29.
//  Copyright © 2022 yuan. All rights reserved.
//

#import "ArraySequence.h"

@implementation ArraySequence

#pragma mark - 1、删除排序数组中的重复项
/**
 输入：[0,0,1,1,1,2,2,3,3,4]
 输出：5, nums = [0,1,2,3,4]
 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
 */
+ (void)removeDuplicates{
    NSMutableArray *nums = @[@0,@0,@1,@1,@1,@2,@2,@3,@3,@4].mutableCopy;
    NSMutableArray *result = @[].mutableCopy;
    for (int i = 0 ; i < nums.count ; i++){
        if (![result containsObject:nums[i]]){
            [result addObject:nums[i]];
        }
    }
    NSLog(@"删除排序数组中的重复项:%@",result);
}

#pragma mark - 2、买卖股票的最佳时机2
/**
 给定一个数组prices，其中prices[i]表示股票第i天的价格。
 在每一天，你可能会决定购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以购买它，然后在同一天出售。
 返回你能获得的最大利润。
 示例1：
 输入：prices = [7,1,5,3,6,4]
 输出：7
 解释：在第2天（股票价格 = 1）的时候买入，在第3天（股票价格 = 5）的时候卖出，这笔交易所能获得利润 = 5 - 1 = 4。
 随后，在第4天（股票价格 = 3）的时候买入，在第5天（股票价格 = 6）的时候卖出，这笔交易所能获得利润 = 6 - 3 = 3。
 */
+ (void)maxProfit{
    NSMutableArray *prices = @[@7,@1,@5,@3,@6,@4].mutableCopy;
    NSInteger res = 0;
    
    for (int i = 0 ; i < prices.count - 1;i++){
        if ([prices[i] integerValue] < [prices[i+1] integerValue]){
            res += ([prices[i+1] integerValue] - [prices[i] integerValue]);
        }
    }
    NSLog(@"买卖股票的最佳时机2:%@",@(res));
}

#pragma mark - 3、旋转数组
/*
 给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

 示例 1:

 输入: nums = [1,2,3,4,5,6,7], k = 3
 输出: [5,6,7,1,2,3,4]
 解释:
 向右轮转 1 步: [7,1,2,3,4,5,6]
 向右轮转 2 步: [6,7,1,2,3,4,5]
 向右轮转 3 步: [5,6,7,1,2,3,4]
 示例 2:

 输入：nums = [-1,-100,3,99], k = 2
 输出：[3,99,-1,-100]
 解释:
 向右轮转 1 步: [99,-1,-100,3]
 向右轮转 2 步: [3,99,-1,-100]
 */

+ (void)rotate{
    NSArray *nums = @[@1,@2,@3,@4,@5,@6,@7];
    NSMutableArray *result = nums.mutableCopy;
    NSInteger k = 3;
    
    //最后一个插到最前面，删除最后一个
    for (int i = 0 ; i < k ; i++){
        [result insertObject:result.lastObject atIndex:0];
        [result removeLastObject];
    }
    NSLog(@"旋转数组：%@",result);
}


#pragma mark - 4、存在重复元素
/**
 输入：nums = [1,1,1,3,3,4,3,2,4,2]
 输出：true
 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
 */
+ (void)containsDuplicates{
    NSArray *nums = @[@0,@0,@1,@1,@1,@2,@2,@3,@3,@4];
    NSMutableSet *set = [NSMutableSet setWithArray:nums];
    BOOL res = nums.count != set.count;
    NSLog(@"存在重复元素:%@",res?@"YES":@"NO");
}

#pragma mark - 5、只出现一次的数字
/*
 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

 说明：
 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

 示例 1:
 输入: [2,2,1]
 输出: 1
 
 示例 2:
 输入: [4,1,2,1,2]
 输出: 4
 */
+ (void)singleNumber{
    NSArray *nums = @[@2,@2,@1];
    NSMutableSet *set = NSMutableSet.set;
    for (id obj in nums){
        if ([set containsObject:obj]){
            [set removeObject:obj];
        }else{
            [set addObject:obj];
        }
    }
    NSLog(@"只出现一次的数字:%@",set.allObjects.firstObject);
}

#pragma mark - 6、两个数组的交集 II
/*
 给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

 示例 1：
 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 输出：[2,2]
 
 示例 2:
 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 输出：[4,9]
 */
+ (void)intersect{
    NSMutableArray *nums1 = @[@4,@9,@5].mutableCopy;
    NSMutableArray *nums2 = @[@9,@4,@9,@8,@4].mutableCopy;
    [nums1 sortUsingComparator:^NSComparisonResult(id  _Nonnull obj1, id  _Nonnull obj2) {
        return obj1 > obj2;
    }];
    [nums2 sortUsingComparator:^NSComparisonResult(id  _Nonnull obj1, id  _Nonnull obj2) {
        return obj1 > obj2;
    }];
    
    int i = 0,j = 0;
    NSInteger n1 = 0,n2 = 0;
    NSMutableArray *results = @[].mutableCopy;
    while (i < nums1.count && j < nums2.count) {
        n1 = [nums1[i] integerValue];
        n2 = [nums2[j] integerValue];
        if (n1 < n2) {
            i += 1;
        } else if (n1 > n2) {
            j += 1;
        } else {
            [results addObject:@(n1)];
            i += 1;
            j += 1;
        }
    }
    NSLog(@"两个数组的交集 II:%@",results);
}


//TODO:找出数组中重复的数字
+ (void)findDuplicates{
//    TICK
    //1、开辟一个新数组B，每次扫描源数组A中的元素，如果不在B中，就加入B中，如果在B中，就找到一个重复的元素
//    NSArray *arr = @[@2,@3,@1,@0,@2,@5,@3];
//    NSMutableArray *result = @[].mutableCopy;
//    for (int i = 0 ; i < arr.count ; i++) {
//        id item = arr[i];
//        if (![result containsObject:item]){
//            [result addObject:item];
//        }else{
//            NSLog(@"findDuplicates:%@",item);
//        }
//    }
//    TOCK
    
    //2、排序 看前后元素是否相等 O(NlogN) 空间 O(1)
    NSArray *array = @[@2,@3,@1,@0,@2,@5,@3];
    NSArray *result = [array sortedArrayUsingComparator:^NSComparisonResult(id _Nonnull obj1, id _Nonnull obj2) {
        return [obj1 compare:obj2];
    }];
    for(int i = 0; i< result.count - 1 ; i++){
        if(result[i] == result[i+1])
        NSLog(@"findDuplicates:%@",result[i]);
    }
}

//TODO:二维数组中的查找
//在一个二位数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
//请完成一个函数，输入这样的一个二位数组和一个整数，判断数组中是否含有该整数
+ (void)findMatrix{
    NSArray *arr = @[
    @[@1,@2,@8,@9],
    @[@2,@4,@9,@12],
    @[@4,@7,@10,@13],
    @[@6,@8,@11,@15]];
    bool find = [self findNumberIn2DArray3:arr target:7];
    NSLog(@"%@",find?@"找到了":@"没找到");
}

//暴力查找：一个元素一个元素的找呗，好简单 空间、时间都击败100%用户
+ (BOOL)findNumberIn2DArray1:(NSArray *)array target:(int)target{
    for (int i = 0 ; i < array.count; i++){
        for (int j = 0; j < ((NSArray *)array[i]).count ; j++){
            if ([array[i][j] integerValue] == target){
                NSLog(@"找到了：%@|%@",@(i),@(j));
                return true;
            }
        }
    }
    return false;
}

//左下角开始查找
+ (BOOL)findNumberIn2DArray2:(NSArray *)array target:(int)target{
    NSInteger i = array.count - 1, j = 0;
    NSInteger rowCount = ((NSArray *)array[0]).count;
    while(i >= 0 && j < rowCount)
    {
        if([array[i][j] integerValue] > target) {
            i--;
        }
        else if([array[i][j] integerValue] < target) {
            j++;
        }
        else {
            NSLog(@"找到了：%@|%@",@(i),@(j));
            return true;
        }
    }
    return false;
}

//从右上角的话，原理和功能都是一样的，用旋转树的解释就是从根节点了
+ (BOOL)findNumberIn2DArray3:(NSArray *)array target:(int)target{
    NSInteger i = 0, j = array.count - 1;
    NSInteger rowCount = ((NSArray *)array[0]).count;
    while(i < rowCount && j >= 0)
    {
        if([array[i][j] integerValue] > target) {
            j--;
        }
        else if([array[i][j] integerValue] < target) {
            i++;
        }
        else {
            NSLog(@"找到了：%@|%@",@(i),@(j));
            return true;
        }
    }
    return false;
}

//TODO:求出这组数字子序列和中最大值
+ (void)findMaxNums{
    NSLog(@"maxNum:%@",[self maxNums]);
}

+ (NSString *)maxNums{
    
    NSString *str = @"12312411";
    NSMutableArray *arr = @[].mutableCopy;
    for (int i = 0 ; i < str.length ; i ++){
        [arr addObject:[NSString stringWithFormat:@"%c",[str characterAtIndex:i]]];
    }
    
    [arr sortUsingComparator:^NSComparisonResult(id  _Nonnull obj1, id  _Nonnull obj2) {
        return [obj1 integerValue] < [obj2 integerValue];
    }];
    
    return [arr componentsJoinedByString:@""];
}

//TODO:合并两个有序数列
+ (void)combinSortArr{
    //1、合并再排序
    NSArray *arr = @[@1,@2,@3,@4];
    NSArray *arr2 = @[@2,@3,@4,@5];
    
    NSMutableArray *resultArr = arr.mutableCopy;
    [resultArr addObjectsFromArray:arr2];
    
    for (int i = 0 ; i < resultArr.count ; i ++){
        for (int j = 0 ; j < resultArr.count - i - 1 ; j ++){
            if ([resultArr[j] integerValue] > [resultArr[j + 1] integerValue]){
                id temp = resultArr[j];
                resultArr[j + 1] = resultArr[j];
                resultArr[j] = temp;
            }
        }
    }
    
//    [resultArr sortUsingComparator:^NSComparisonResult(id  _Nonnull obj1, id  _Nonnull obj2) {
//        return [obj1 integerValue] > [obj2 integerValue];
//    }];
    
    NSLog(@"%@",resultArr);
}

+ (void)combinSortArr2{
    //2、双指针
    NSArray *a = @[@1,@2,@3,@4];
    NSArray *b = @[@2,@3,@4,@5];
    NSMutableArray *result = @[].mutableCopy;
    
    NSInteger aLen = a.count, bLen = b.count;

    // p 是a数组的下标，q是b数组的下标，i是result数组的下标
    int aIndex = 0, bIndex = 0, rIndex = 0;
    
    // 如果两个数组都还有剩余数据没有放到result数组
    while (aIndex < aLen && bIndex < bLen) {
       if ([a[aIndex] integerValue] <= [b[bIndex] integerValue]) {
           result[rIndex++] = a[aIndex++];
       } else {
           result[rIndex++] = b[bIndex++];
       }
    }
    // 如果a数组还有剩余数据
    while (aIndex < aLen) {
       result[rIndex++] = a[aIndex++];
    }
    // 如果b数组还有剩余数据
    while (bIndex < bLen) {
       result[rIndex++] = b[bIndex++];
    }
    
    NSLog(@"%@",result);
}


@end
